package dataStructure.Sort;

import java.util.Arrays;

public class QuickSort {
    /**
     * 快速排序
     * 双边循环快排
     *
     * @param nums  要排序的数组
     * @param left  数组的左边界
     * @param right 数组的右边界
     */
    public static void quickSort(int[] nums, int left, int right) {
        if (left >= right) return;//数组为空或或者只有一个元素,不用排序

        int pivotIndex = partition(nums, left, right);
        quickSort(nums, left, pivotIndex - 1);
        quickSort(nums, pivotIndex + 1, right);
    }

    /**
     * 将pivot放到合适的位置,并返回该位置
     *
     * @param nums  要排序的数组
     * @param left  数组的左边界
     * @param right 数组的右边界
     * @return pivot下标
     */
    public static int partition(int[] nums, int left, int right) {
        int pivot = nums[left];
        int i = left;
        int j = right;

        while (i < j) {
            //j从右往左找小的
            while (i < j && nums[j] >= pivot) j--;

            //i从左往右找大的
            while (i < j && nums[i] <= pivot) i++;

            //交换i和j指向的元素
            swap(nums, i, j);
        }

        //最后把pivot放到"中间"
        swap(nums, left, i);
        return i;
    }

    public static void swap(int[] nums, int i, int j) {
        int tem = nums[i];
        nums[i] = nums[j];
        nums[j] = tem;
    }

    public static void quickSort(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
    }

    public static void main(String[] args) {
        int[] nums = new int[]{49, 38, 65, 97, 76, 13, 27, 49};
        partition(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
    }
}
